home *** CD-ROM | disk | FTP | other *** search
/ The Atari Compendium / The Atari Compendium (Toad Computers) (1994).iso / files / prgtools / editors / mutt / me2s_pl7.zoo / mu_edit2 / util / regex.c < prev    next >
Encoding:
C/C++ Source or Header  |  1993-07-05  |  22.7 KB  |  703 lines
  1. static char rcsid[] = "$Id: regex.c,v 1.1 1992/09/06 19:31:32 mike Exp $";
  2.  
  3. /* $Log: regex.c,v $
  4.  * Revision 1.1  1992/09/06  19:31:32  mike
  5.  * Initial revision
  6.  *
  7.  */
  8.  
  9. /*
  10.  * regex - Regular expression pattern matching
  11.  *         and replacement
  12.  *
  13.  * By:  Ozan S. Yigit (oz), Dept. of Computer Science, York University
  14.  * Mods: C Durland
  15.  *
  16.  * These routines are the PUBLIC DOMAIN equivalents of regex routines as
  17.  * found in 4.nBSD UN*X, with minor extensions.
  18.  *
  19.  * These routines are derived from various implementations found in software
  20.  * tools books, and Conroy's grep.  They are NOT derived from
  21.  * licensed/restricted software.  For more interesting/academic/complicated
  22.  * implementations, see Henry Spencer's regexp routines, or GNU Emacs
  23.  * pattern matching module.
  24.  *
  25.  * dfa = deterministic finite automata
  26.  * Routines:
  27.  *  re_comp: compile a regular expression into a DFA.
  28.  *    char *re_comp(s)
  29.  *    char *s;
  30.  *    returns: NULL if OK, else error string
  31.  *    If s is NULL or 0 length, last compiled pattern is used.
  32.  *  re_exec: execute the DFA to match a pattern.
  33.  *    int re_exec(s)
  34.  *    char *s;
  35.  *  re_subs: substitute the matched portions in a new string.
  36.  *    int re_subs(src, dst)
  37.  *    char *src;
  38.  *    char *dst;
  39.  *  re_fail:    failure routine for re_exec.
  40.  *    void re_fail(msg, op)
  41.  *    char *msg;
  42.  *    char op;
  43.  *  
  44.  * Regular Expressions:
  45.  *
  46.  *      [1]     char    matches itself, unless it is a special
  47.  *                      character (metachar): . \ [ ] * + ^ $
  48.  *
  49.  *      [2]     .       matches any character.
  50.  *
  51.  *      [3]     \       matches the character following it, except
  52.  *            when followed by one of: ()123456789<> adnwW
  53.  *            (see [7], [8] and [9])
  54.  *            It is used as an escape character for all other
  55.  *            meta-characters, and itself.  When used in a set
  56.  *            ([4]), it is treated as an ordinary character.
  57.  *
  58.  *      [4]     [set]   matches one of the characters in the set.
  59.  *                      If the first character in the set is "^",
  60.  *                      it matches a character NOT in the set. A
  61.  *                      shorthand S-E is used to specify a set of
  62.  *                      characters S upto E, inclusive. The special
  63.  *                      characters "]" and "-" have no special
  64.  *                      meaning if they appear as the first chars
  65.  *                      in the set.
  66.  *                      Example:   Matches:
  67.  *            --------   -------
  68.  *            [a-z]       Any lowercase alpha.
  69.  *
  70.  *            [^]-]      Any char except ] and -.
  71.  *
  72.  *            [^A-Z]     Any char except uppercase alpha.
  73.  *
  74.  *            [a-zA-Z]   Any alpha.
  75.  *
  76.  *                      [a-b-c] == [a-bb-c] == [a-c]
  77.  *                      [a-a] == [a]
  78.  *            [-abc] == [abc-]  Match -, a, b, c.
  79.  *
  80.  *            []] == ]   Match "]"
  81.  *            [-]]       Match only "-]".  This is a set ([-])
  82.  *                   and a character (]).
  83.  *            
  84.  *            [z-a]      Nothing and is an error.
  85.  *
  86.  *      [5]     *       any regular expression form [1] to [4], followed by
  87.  *                      closure char (*) matches zero or more matches of
  88.  *                      that form.
  89.  *
  90.  *      [6]     +       same as [5], except it matches one or more.
  91.  *
  92.  *      [7]             a regular expression in the form [1] to [10], enclosed
  93.  *                      as \(form\) matches what form matches. The enclosure
  94.  *                      creates a set of tags, used for [8] and for
  95.  *                      pattern substution. The tagged forms are numbered
  96.  *            starting from 1.
  97.  *
  98.  *      [8]             a \ followed by a digit 1 to 9 matches whatever a
  99.  *                      previously tagged regular expression ([7]) matched.
  100.  *
  101.  *    [9]    \<    a regular expression starting with a \< construct
  102.  *        \>    and/or ending with a \> construct, restricts the
  103.  *            pattern matching to the beginning of a word, and/or
  104.  *            the end of a word. A word is defined to be a character
  105.  *            string beginning and/or ending with the characters
  106.  *            A-Z a-z 0-9 and _. It must also be preceded and/or
  107.  *            followed by any character outside those mentioned.
  108.  *
  109.  *      [10]            a composite regular expression xy where x and y
  110.  *                      are in the form [1] to [10] matches the longest
  111.  *                      match of x followed by a match for y.
  112.  *
  113.  *      [11]    ^    a regular expression starting with a ^ character
  114.  *        $    and/or ending with a $ character, restricts the
  115.  *                      pattern matching to the beginning of the line,
  116.  *                      or the end of line. [anchors] Elsewhere in the
  117.  *            pattern, ^ and $ are treated as ordinary characters.
  118.  *
  119.  * Acknowledgements:
  120.  *   HCR's Hugh Redelmeier has been most helpful in various stages of
  121.  *   development.  He convinced me to include BOW and EOW constructs,
  122.  *   originally invented by Rob Pike at the University of Toronto.
  123.  * References:
  124.  *   Software tools        Kernighan & Plauger
  125.  *   Software tools in Pascal    Kernighan & Plauger
  126.  *   Grep [rsx-11 C dist]    David Conroy
  127.  *   ed - text editor        Un*x Programmer's Manual
  128.  *   Advanced editing on Un*x    B. W. Kernighan
  129.  *   RegExp routines        Henry Spencer
  130.  * Notes:
  131.  *  This implementation uses a bit-set representation for character sets for
  132.  *    speed and compactness.  Each character is represented by one bit in a
  133.  *    N-bit block.  Thus, SET or NSET always takes a constant M bytes in the
  134.  *    internal dfa, and re_exec does a single bit comparison to locate the
  135.  *    character in the set.  N is 128 for 7 bits ASCII and 256 for 8 bit
  136.  *    data.  Thus M is 16 or 32 bytes.
  137.  *  Put CLO in front of what gets closed for ease of interpreting.
  138.  *  Put END at end of what gets closed to limit recursion.
  139.  * Examples:
  140.  *    pattern:    foo*.*
  141.  *    compile:    CHR f CHR o CLO CHR o END CLO ANY END END
  142.  *    matches:    fo foo fooo foobar fobar foxx ...
  143.  *
  144.  *    pattern:    fo[ob]a[rz]    
  145.  *    compile:    CHR f CHR o SET bitset CHR a SET bitset END
  146.  *    matches:    fobar fooar fobaz fooaz
  147.  *
  148.  *    pattern:    foo\\+
  149.  *    compile:    CHR f CHR o CHR o CHR \ CLO CHR \ END END
  150.  *    matches:    foo\ foo\\ foo\\\  ...
  151.  *
  152.  *    pattern:    \(foo\)[1-3]\1    (same as foo[1-3]foo)
  153.  *    compile:    BOT 1 CHR f CHR o CHR o EOT 1 SET bitset REF 1 END
  154.  *    matches:    foo1foo foo2foo foo3foo
  155.  *
  156.  *    pattern:    \(fo.*\)-\1
  157.  *    compile:    BOT 1 CHR f CHR o CLO ANY END EOT 1 CHR - REF 1 END
  158.  *    matches:    foo-foo fo-fo fob-fob foobar-foobar ...
  159.  */
  160.  
  161. #include <char.h>
  162. #include <const.h>
  163.  
  164. typedef unsigned char Char;
  165.  
  166. #define MAXDFA 768    /* amount of space for compiled RE */
  167. #define MAXTAG  10
  168.  
  169. #define CHR     1    /* character        :: CHR<character> */
  170. #define ANY     2    /* .            :: ANY */
  171. #define SET     3    /* set: [...]        :: SET bitset */
  172. #define NSET     4    /* not set: [^...]    :: SET bitset */
  173. #define BOL     5    /* beginning of line: ^ :: BOL */
  174. #define EOL     6    /* end of line: $    :: EOL */
  175. #define BOT     7    /* beginning of tag: \( */
  176. #define EOT     8    /* end of tag: \) */
  177. #define BOW     9    /* beginning of word: \< */
  178. #define EOW    10    /* end of word: \> */
  179. #define REF    11    /* tag reference: \1,...,\9 */
  180. #define CLO    12    /* closure: +, *    :: CLO dfa END */
  181. #define SPACE    13    /* ": ": match isspace() */
  182. #define ALPHA    14    /* :a    match isalpha() */
  183. #define DIGIT    15    /* :d     match isdigit() */
  184. #define ALNUM    16    /* :n    match isalnum() */
  185. #define WORD    17    /* :w    match isword() */
  186. #define NWORD    18    /* :W    match !isword() */
  187.  
  188. #define END     0
  189.  
  190. /* ******************************************************************** */
  191. /* **************************** Bit Tables **************************** */
  192. /* ******************************************************************** */
  193.  
  194. /* 
  195.  * Bit table:  a string of bits stored in an array of char
  196.  *     .-----------------------------------.
  197.  *     |01234567|89012345|67890123|45678901|
  198.  *     `-----------------------------------'
  199.  *    bits[0]      [1]      [2]      [3]
  200.  * To find what bucket the nth bit is in (8 bits per bucket):
  201.  *       bit_bucket(n) = bits[n/8]
  202.  *   It might be a good idea to restrict n so it doesn't index outside its
  203.  *     range (only works if number of bits is a power of 2):
  204.  *       n = n & ((max_n - 1) & ~7)  where max_n is a power of 2
  205.  *     The ~7 is just to get rid of the lower bits that won't do anything
  206.  *     anyway.
  207.  * The nth bit in the bucket is n mod 8 (ie the lower 3 bits of n (0-7) are
  208.  *   the bit position):
  209.  *       bit_flag(n) = 1 << (n & 7)
  210.  * To find the state of the nth bit (0 == off and !0 == on):
  211.  *       bit_bucket(n) & bit_flag(n)
  212.  * To set the nth bit:
  213.  *       bits[bit_bucket(n)] |= bit_flag(n)
  214.  * Notes:
  215.  *   The bits are stored in a character array so that the array can be
  216.  *     easily copied without worrying about alignment (ie can use a loop as
  217.  *     well as memcpy()).
  218.  *   This is based on two's complement math.
  219.  */
  220.  
  221. /* The following defines are for character set size.  128 for straight
  222.  *   ASCII, 256 for Euro ASCII (8 bit characters).
  223.  */
  224. #define MAXCHR    256        /*  128 or  256 */
  225. #define BLKIND    0xf8        /* 0x78 or 0xf8 */
  226.  
  227. /*
  228.  * The following defines are not meant to be changeable.
  229.  * They are for readability only.
  230.  */
  231. #define CHRBIT    8
  232. #define BITBLK    MAXCHR/CHRBIT
  233. #define BITIND    0x7
  234.  
  235. static Char bittab[BITBLK];    /* bit table for SET */
  236.  
  237.     /* Add or check to see if a character is in the bit table (character
  238.      *   set).
  239.      * Note:
  240.      *   When calling these routines, make sure c is an unsigned char (or
  241.      *     int) so if it has the high bit set, casting it to an int won't
  242.      *     make it a large negative number.
  243.      */
  244. #define ISINSET(bittab,c) ((bittab)[((c) & BLKIND)>>3] & (1<<((c) & BITIND)))
  245. #define   CHSET(bittab,c)  (bittab)[((c) & BLKIND)>>3] |= 1<<((c) & BITIND)
  246.  
  247. static void chset(c) register int c; { CHSET(bittab,c); }
  248.  
  249. /* ******************************************************************** */
  250.  
  251. #define SLOP    50        /* dfa overflow protection */
  252.  
  253. static Char dfa[MAXDFA + SLOP];    /* automaton */
  254. static int
  255.   tagstk[MAXTAG],        /* subpat tag stack */
  256.   pattern_compiled = FALSE;    /* status of lastpat */
  257.  
  258. #define BADPAT(msg)    return (*dfa = END, (Char *)msg)
  259. #define STORE(x)    (*mp++ = x)  /* !!! should check for dfa overflow */
  260.  
  261.     /* Compile RE to internal format & store in dfa[]
  262.      * Input:
  263.      *   pat : pointer to regular expression string to compile.
  264.      * Returns:
  265.      *   NULL:  RE compiled OK.
  266.      *   pointer to error message.
  267.      */
  268. Char *re_comp(pat) Char *pat;
  269. {
  270.   register Char
  271.     *p,            /* pattern pointer */
  272.     *mp = dfa,        /* dfa pointer */
  273.     *lp,        /* saved pointer */
  274.     *sp = dfa;        /* another one */
  275.   register int
  276.     tagi = 0,        /* tag stack index */
  277.     tagc = 1,        /* actual tag count */
  278.     n;
  279.  
  280.   if (pat == NULL || *pat == '\0')
  281.     if (pattern_compiled) return NULL;
  282.     else BADPAT("No previous regular expression");
  283.  
  284.   pattern_compiled = FALSE;
  285.  
  286.   *dfa = END;            /* init dfa for lp and sp */
  287.  
  288.   for (p = pat; *p; p++)
  289.   {
  290.     lp = mp;            /* start of next dfa state */
  291.     switch(*p)
  292.     {
  293.       case '.': STORE(ANY); break;        /* match any character */
  294.       case '^':                    /* match beginning of line */
  295.     if (p == pat) STORE(BOL);
  296.     else { STORE(CHR); STORE(*p); }        /* match ^ */
  297.     break;
  298.       case '$':                    /* match end of line */
  299.     if (*(p+1) == '\0') STORE(EOL);
  300.     else { STORE(CHR); STORE(*p); }        /* match $ */
  301.     break;
  302.       case '[':                    /* match a set of characters */
  303.     if (*++p == '^') { STORE(NSET); p++; } else STORE(SET);
  304.     if (*p == ']') chset(*p++);        /* real bracket, match ] */
  305.     if (*p == '-') chset(*p++);        /* real dash, match - */
  306.     while (*p && *p != ']')
  307.     {
  308.       if (*p == '-' && *(p+1) != '\0' && *(p+1) != ']')    /* [a-z] */
  309.       {
  310.         int c1, c2;
  311.  
  312.         p++;
  313.         c1 = *(p-2);    /* 'a' */
  314.         c2 = *p++;        /* 'z' */
  315.         if (c1 > c2) BADPAT("Empty set");    /* something like [z-a] */
  316.         /* remember that 'a' has already been put into bittab */
  317.         while (++c1 <= c2) chset(c1);    /* build bit table */
  318.       }
  319. #ifdef EXTEND
  320.       else if (*p == '\\' && *(p+1)) { p++; chset(*p++); }
  321. #endif
  322.       else chset(*p++);
  323.     }
  324.     if (*p == '\0') BADPAT("Missing ]");
  325.     for (n = 0; n < BITBLK; bittab[n++] = '\0') STORE(bittab[n]);
  326.     break;
  327.       case '*':                /* match 0 or more of preceding RE */
  328.       case '+':            /* match 1 or more.  Note: x+ == xx* */
  329.     if (p == pat) BADPAT("Empty closure");
  330.     lp = sp;        /* previous opcode */
  331.     if (*lp == CLO) break;    /* equivalence: x** == x*  */
  332.     switch(*lp)
  333.     {
  334.       case BOL: case BOT: case EOT: case BOW: case EOW: case REF:
  335.         BADPAT("Illegal closure");
  336.     }
  337.     if (*p == '+') for (sp = mp; lp < sp; lp++) STORE(*lp);
  338.     STORE(END); STORE(END); sp = mp;
  339.     while (--mp > lp) *mp = mp[-1]; STORE(CLO);    /* open hole for CLO */
  340.     mp = sp;
  341.     break;
  342.       case '\\':                      /* tags, backrefs */
  343.     switch(*++p)
  344.     {
  345.       case '\0': BADPAT("Bad quote");
  346.       case '(':
  347.         if (tagc < MAXTAG)
  348.           { tagstk[++tagi] = tagc; STORE(BOT); STORE(tagc++); }
  349.         else BADPAT("Too many \\(\\) pairs");
  350.         break;
  351.       case ')':
  352.         if (*sp == BOT) BADPAT("Null pattern inside \\(\\)");
  353.         if (tagi > 0) { STORE(EOT); STORE(tagstk[tagi--]); }
  354.         else BADPAT("Unmatched \\)");
  355.         break;
  356.       case '<': STORE(BOW); break;
  357.       case '>':
  358.         if (*sp == BOW) BADPAT("Null pattern inside \\<\\>");
  359.         STORE(EOW);
  360.         break;
  361.       case '1': case '2': case '3': case '4': case '5': case '6': 
  362.       case '7': case '8': case '9':
  363.         n = *p - '0';
  364.         if (tagi > 0 && tagstk[tagi] == n) BADPAT("Cyclical reference");
  365.         if (tagc > n) { STORE(REF); STORE(n); }
  366.         else BADPAT("Undetermined reference");
  367.         break;
  368.       case ' ': STORE(SPACE); break;
  369.       case 'a': STORE(ALPHA); break;
  370.       case 'd': STORE(DIGIT); break;
  371.       case 'n': STORE(ALNUM); break;
  372.       case 'w': STORE(WORD);  break;
  373.       case 'W': STORE(NWORD); break;
  374. #ifdef EXTEND
  375.       case 'b': STORE(CHR); STORE('\b'); break;
  376.       case 'n': STORE(CHR); STORE('\n'); break;
  377.       case 'f': STORE(CHR); STORE('\f'); break;
  378.       case 'r': STORE(CHR); STORE('\r'); break;
  379.       case 't': STORE(CHR); STORE('\t'); break;
  380. #endif
  381.       default: STORE(CHR); STORE(*p);
  382.     }
  383.     break;
  384.       default : STORE(CHR); STORE(*p); break;    /* an ordinary character */
  385.     }
  386.     sp = lp;        /* start of previous state */
  387.  
  388.     if (mp > dfa + MAXDFA) BADPAT("Pattern too long (braindead re_comp())");
  389.   }
  390.  
  391.   if (tagi > 0) BADPAT("Unmatched \\(");
  392.  
  393.   STORE(END);
  394.  
  395.   pattern_compiled = TRUE;
  396.  
  397.   return NULL;
  398. }
  399.  
  400. static Char *pmatch();
  401.  
  402. Char *bopat[MAXTAG], *eopat[MAXTAG];
  403. int re_errorcode;    /* sleaze */
  404.  
  405. static Char *bol;
  406.  
  407. /* re_exec:  execute dfa to find a match.
  408.  *
  409.  * special cases: (dfa[0])    
  410.  *  BOL
  411.  *    Match only once, starting from the beginning.
  412.  *  CHR
  413.  *    First locate the character without calling pmatch(), and if found,
  414.  *    call pmatch() for the remaining string.
  415.  *  END
  416.  *    re_comp() failed, poor luser did not check for it. Fail fast.
  417.  *
  418.  * If a match is found, bopat[0] and eopat[0] are set to the beginning and
  419.  *   the end of the matched fragment, respectively.
  420.  *
  421.  * Input:
  422.  *   lp: string to search
  423.  *   SoL==TRUE if lp starts line
  424.  *   move==TRUE if search the entire string for match
  425.  * Returns:
  426.  *   TRUE:  
  427.  *   FALSE:  
  428.  *   ????
  429.  * Munges:
  430.  *   re_errorcode: Set to FALSE, re_fail() might want to set it.
  431.  * Notes:
  432.  *   If SoL is FALSE, lp[-1] MUST be at valid!  A couple of REs will look
  433.  *     there if they can.
  434.  */
  435. int re_exec(lp,SoL,move) register Char *lp; int SoL, move;
  436. {
  437.   register Char *ap = dfa, c;
  438.   Char *ep = NULL;
  439.  
  440.   re_errorcode = FALSE;        /* assume no match */
  441.   bol = (SoL ? lp : NULL);
  442.  
  443.   bopat[0] = bopat[1] = bopat[2] = bopat[3] = bopat[4] = bopat[5] = 
  444.   bopat[6] = bopat[7] = bopat[8] = bopat[9] = NULL;
  445.  
  446.   switch(*ap)
  447.   {
  448.     case END: return FALSE;        /* munged automaton. fail always */
  449.     case BOL:                /* anchored: match from BOL only */
  450.       if (!SoL) return FALSE;        /* BoL can only be at front of dfa */
  451.       ep = pmatch(lp,++ap);
  452.       break;
  453.     case CHR:                /* ordinary char: locate it fast */
  454.       if (move)
  455.       {
  456.     c = *(ap+1);
  457.     while (*lp && !ceq(*lp,c)) lp++;
  458.     if (!*lp) return FALSE;        /* if EoS, fail. else fall thru */
  459.       }
  460.     default:                /* regular matching all the way. */
  461.       if (!move) { ep = pmatch(lp,ap); break; }
  462. #if 0
  463.       while (*lp)
  464.       {
  465.     if ((ep = pmatch(lp,ap))) break;
  466.     lp++;
  467.       }
  468. #else
  469.       while (TRUE)
  470.       {
  471.     if ((ep = pmatch(lp,ap))) break;
  472.     if ('\0' == *lp++) break;
  473.       }
  474. #endif
  475.       break;
  476.   }
  477.   if (!ep) return re_errorcode;        /* only if pmatch() returns NULL */
  478.  
  479.   bopat[0] = lp; eopat[0] = ep; 
  480.  
  481.   return TRUE;
  482. }
  483.  
  484. /* 
  485.  * pmatch: internal routine for the hard part
  486.  *
  487.  * This code is mostly snarfed from an early grep written by David Conroy.
  488.  *   The backref and tag stuff, and various other mods are by oZ.
  489.  *
  490.  * special cases: (dfa[n], dfa[n+1])
  491.  *  CLO ANY
  492.  *    We KNOW ".*" will match ANYTHING upto the end of line.  Thus, go to
  493.  *    the end of line straight, without calling pmatch() recursively.  As in
  494.  *    the other closure cases, the remaining pattern must be matched by
  495.  *    moving backwards on the string recursively, to find a match for xy (x
  496.  *    is ".*" and y is the remaining pattern) where the match satisfies the
  497.  *    LONGEST match for x followed by a match for y.
  498.  *  CLO CHR
  499.  *    Scan forward matching the single char without recursion, and at the
  500.  *    point of failure, we execute the remaining dfa recursively, as
  501.  *    described above.
  502.  *
  503.  * At the end of a successful match, bopat[n] and eopat[n] are set to the
  504.  *   beginning and end of subpatterns matched by tagged expressions (n = 1
  505.  *   to 9).
  506.  * 
  507.  * Input:
  508.  * Returns:
  509.  *   NULL: No match, re_fail() may have been called.
  510.  *   else: pointer to end of match.
  511.  */
  512.  
  513. extern void re_fail();
  514.  
  515.     /* skip values for CLO XXX to skip past the closure */
  516. #define ANYSKIP    2         /* CLO ANY END ...       */
  517. #define CHRSKIP    3        /* CLO CHR chr END ...       */
  518. #define SETSKIP (2 +BITBLK)    /* CLO SET 16bytes END ... */
  519.  
  520. static Char *pmatch(lp,dfa) register Char *lp, *dfa;
  521. {
  522.   register Char
  523.     *e,            /* extra pointer for CLO */
  524.     *bp, *ep;        /* beginning and ending of subpat */
  525.   Char *are;        /* to save the line ptr */
  526.   register int op, c, n;
  527.  
  528.   while ((op = *dfa++) != END)
  529.     switch(op)
  530.     {
  531.       case CHR:    if (!ceq(*lp++,*dfa++)) return NULL; break;
  532.       case ANY: if (*lp++ == '\0')      return NULL; break;
  533.       case SET:
  534.         c = *lp++;
  535.     if (!ISINSET(dfa,c)) return NULL;    /* ISINSET(dfa,0) is FALSE */
  536.     dfa += BITBLK;
  537.     break;
  538.       case NSET:
  539.     if ((c = *lp++) == '\0' || ISINSET(dfa,c)) return NULL;
  540.     dfa += BITBLK;
  541.     break;
  542.       case BOT: bopat[*dfa++] = lp; break;
  543.       case EOT: eopat[*dfa++] = lp; break;
  544.       case EOL:   if (*lp != '\0')            return NULL; break;
  545.       case ALNUM: if (!isalnum(*lp++))            return NULL; break;
  546.       case ALPHA: if (!isalpha(*lp++))             return NULL; break;
  547.       case DIGIT: if (!isdigit(*lp++))            return NULL; break;
  548.       case SPACE: if (!isspace(*lp++))            return NULL; break;
  549.       case WORD:  if (!isword (*lp++))            return NULL; break;
  550.       case NWORD: if (*lp == '\0' || isword(*lp++)) return NULL; break;
  551.       case BOW:
  552.         if (!(lp != bol && isword(lp[-1])) && isword(*lp)) break;
  553.     return NULL;
  554.       case EOW:        /* 'w\0' is OK here */
  555.         if ((lp != bol && isword(lp[-1])) && !isword(*lp)) break;
  556.     return NULL;
  557.       case REF:        /* !!! case_fold? */
  558.         n = *dfa++; bp = bopat[n]; ep = eopat[n];
  559.     while (bp < ep) if (*bp++ != *lp++) return NULL;  /* !!! recurse? */
  560.     break;
  561.       case CLO:
  562.         are = lp; n = ANYSKIP;
  563.     switch(*dfa)
  564.     {
  565.       case ANY:   while (*lp)          lp++; break;
  566.       case ALNUM: while (isalnum(*lp)) lp++; break;
  567.       case ALPHA: while (isalpha(*lp)) lp++; break;
  568.       case DIGIT: while (isdigit(*lp)) lp++; break;
  569.       case SPACE: while (isspace(*lp)) lp++; break;
  570.       case WORD:  while (isword (*lp)) lp++; break;
  571.       case NWORD: while (*lp && !isword(*lp)) lp++; break;
  572.       case CHR:
  573.         c = *(dfa+1);        /* we know c!='\0' */
  574.         while (ceq(*lp,c)) lp++;
  575.         n = CHRSKIP;
  576.         break;
  577.       case SET: case NSET:
  578.         while (*lp && (e = pmatch(lp,dfa))) lp = e;
  579.         n = SETSKIP;
  580.         break;
  581.       default: re_fail("closure: bad dfa.",*dfa); return NULL;
  582.     }
  583.     dfa += n;
  584.     while (lp >= are)    /* backup up till match next pattern */
  585.     {
  586.       if (e = pmatch(lp,dfa)) return e;
  587.       --lp;
  588.     }
  589.     return NULL;
  590.       default: re_fail("re_exec: bad dfa.",op); return NULL;
  591.     }
  592.   return lp;
  593. }
  594.  
  595. /*
  596.  * re_subs: substitute the matched portions of the src in dst.
  597.  *    &    substitute the entire matched pattern.
  598.  *    \digit    substitute a subpattern, with the given
  599.  *        tag number. Tags are numbered from 1 to
  600.  *        9. If the particular tagged subpattern
  601.  *        does not exist, null is substituted.
  602.  *     !!!Note: if the line that was used re_exec() has gone byebye
  603.  *      then \digit will blow cookies since the tags point into the line.
  604.  * Input:
  605.  *   src:
  606.  *   dst:
  607.  * Returns:
  608.  *   TRUE:   everything went as expected
  609.  *   FALSE:  Bad src or no match.
  610.  */
  611. int re_subs(src,dst) register Char *src, *dst;
  612. {
  613.   register Char c, *bp, *ep;
  614.   register int pin;
  615.  
  616.   if (!bopat[0]) return FALSE;
  617.  
  618.   while (c = *src++)
  619.   {
  620.     switch(c)
  621.     {
  622.       case '&': pin = 0; break;
  623.       case '\\': 
  624.         c = *src++;
  625.     if (c >= '0' && c <= '9') { pin = c - '0'; break; }
  626.       default: *dst++ = c; continue;
  627.     }
  628.     if ((bp = bopat[pin]) && (ep = eopat[pin]))
  629.     {
  630.       while (*bp && bp < ep) *dst++ = *bp++;
  631.       if (bp < ep) return FALSE;
  632.     }
  633.   }
  634.   *dst = '\0';
  635.  
  636.   return TRUE;
  637. }
  638.  
  639. /* ******************************************************************** */
  640. /* ************************* DEBUG ************************************ */
  641. /* ******************************************************************** */
  642.  
  643. #ifdef DEBUG
  644. /*
  645.  * symbolic - produce a symbolic dump of the dfa
  646.  */
  647. symbolic(s) 
  648. char *s;
  649. {
  650.     printf("pattern: %s\n", s);
  651.     printf("dfacode:\n");
  652.     dfadump(dfa);
  653. }
  654.  
  655. static    
  656. dfadump(dfa) Char *dfa;
  657. {
  658.   register int n;
  659.  
  660.   while (*dfa != END)
  661.     switch(*dfa++)
  662.     {
  663.       case CLO:
  664.         printf("CLOSURE");
  665.     dfadump(dfa);
  666.     switch(*dfa)
  667.     {
  668.       case CHR: n = CHRSKIP; break;
  669.       case ANY: n = ANYSKIP; break;
  670.       case SET: case NSET: n = SETSKIP; break;
  671.     }
  672.     dfa += n;
  673.     break;
  674.       case CHR: printf("\tCHR %c\n",*dfa++); break;
  675.       case ANY: printf("\tANY .\n"); break;
  676.       case BOL: printf("\tBOL -\n"); break;
  677.       case EOL: printf("\tEOL -\n"); break;
  678.       case BOT: printf("BOT: %d\n",*dfa++); break;
  679.       case EOT: printf("EOT: %d\n",*dfa++); break;
  680.       case BOW: printf("BOW\n"); break;
  681.       case EOW: printf("EOW\n"); break;
  682.       case REF: printf("REF: %d\n",*dfa++); break;
  683.       case SET:
  684.         printf("\tSET [");
  685.     for (n = 0; n < MAXCHR; n++)
  686.       if (ISINSET(dfa,n)) printf("%c",n);
  687.     printf("]\n");
  688.     dfa += BITBLK;
  689.     break;
  690.       case NSET:
  691.         printf("\tNSET [");
  692.     for (n = 0; n < MAXCHR; n++)
  693.       if (ISINSET(dfa,n)) printf("%c",n);
  694.     printf("]\n"); dfa += BITBLK;
  695.     break;
  696.       default:
  697.         printf("bad dfa. opcode %o\n", dfa[-1]);
  698.     exit(1);
  699.     break;
  700.     }
  701. }
  702. #endif
  703.